#include<iostream>
#include<vector>
using namespace std;
/*
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方;
换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
解题思路：
该题目可看作是从一个完全平方数序列中求出能够装满背包容量为n的最少完全平方数的个数，转化为完全背包问题
dp[j]表示的是装满容量为j的背包所需要的最少完全平方数
dp[j] = min(dp[j-i*i]+1,dp[j])
*/
int dp(int n)
{
    //创建dp数组
    vector<int> dp(n+1,INT_MAX);
    dp[0] = 0;
    //遍历dp数组,先遍历物品再遍历背包
    for(int i=1;i*i<=n;i++)
    {
        for(int j=i*i;j<=n;j++)
        {
            dp[j] = min(dp[j-i*i]+1,dp[j]);
        }   
    }
    return dp[n];
}
int main()
{
    cout<<"enter a n:"<<endl;
    int n;
    cin>>n;
    cout<<dp(n);
    return 0;
}